// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem85.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=85 lang=cpp
 *
 * [85] 最大矩形
 */

// @lc code=start
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int max = 0;
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i = 0 ; i < m; i++)
            for(int j = 0 ; j < n;j++)
            {
                if(matrix[i][j] == '1')
                {        
                    if(i == 0 || j == 0)
                    {
                        dp[i][j] = 1;
                        continue;
                    }
                    else
                    {
                        dp[i][j] = max((dp[i-1][j] + 1), (dp[i][j-1] + 1));
                    }
                    if(max < dp[i][j])
                        max = dp[i][j];
                }
                else
                {
                    dp[i][j] = 0;
                }
            }
         return max;
    }
};
// @lc code=end

